#include "main/utils.h"
using namespace std;

int countOfIntegers(int digit) {
  if (digit == 1)
    return 10;
  return pow(10, digit - 1) * 9;
}

int beginNumber(int digit) {
  if (digit == 1)
    return 0;
  return pow(10, digit - 1);
}

int digitAtIndex(int index, int digit) {
  int begin_num = beginNumber(digit) + index / digit;
  int index_from_right = digit - index % digit;
  for (int i = 1; i < index_from_right; ++i)
    begin_num /= 10;
  return begin_num % 10;
}

int digitAtIndex(int index) {
  if (index < 0)
    return -1;

  int digit = 1;
  while (1) {
    // digit位数有几个
    int numbers = countOfIntegers(digit);
    if (index < numbers * digit)
      // digit位数中，index位是多少
      return digitAtIndex(index, digit);
    index -= numbers * digit;
    ++digit;
  }
  return -1;
}

int main() {
  int index = 1001;
  int ret = digitAtIndex(index);
  cout << "The digit at index 1001 is: " << ret << " expected: 7" << endl;

  index = 189;
  ret = digitAtIndex(index);
  cout << "The digit at index 1001 is: " << ret << " expected: 9" << endl;
  
  index = 1000;
  ret = digitAtIndex(index);
  cout << "The digit at index 1001 is: " << ret << " expected: 3" << endl;

  return 0;
}
